#ifndef LINKLIST_H
#define LINKLIST_H

#include<iostream>
using namespace std;

#define ERROE NULL

// 构建一个节点类
class Node
{
public:
    int data;    //代表数据域
    Node * next; //代表指针域，指向直接后继元素
};

// 构建一个单链表类
class linkList:public Node
{
private:
    Node * head;

public:
    linkList();     // 构建一个单链表;
    ~linkList();    // 销毁一个单链表;

public:
    void createLinkList(int n);             // 创建一个单链表
    void travalLinkList();                  // 遍历线性表
    int getLength();                        // 获取线性表长度
    bool IsEmpty();                         // 判断单链表是否为空
    Node * findNode(int data);              // 查找节点
    void insertElemAtEnd(int data);         // 在尾部插入指定的元素
    void insertElemAtIndex(int data, int n);// 在指定位置插入指定元素
    void insertElemAtHead(int data);        // 在头部插入指定元素
    void deleteElemAtEnd();                 // 在尾部删除元素
    void deleteAll();                       // 删除所有数据
    void deleteElemAtPoint(int data);       // 删除指定的数据
    void deleteElemAtHead();                // 在头部删除节点

public:
    // 单链表反转 http://c.biancheng.net/view/8105.html
    //迭代反转法，head 为无头节点链表的头指针;
    //从当前链表的首元节点开始，一直遍历至链表的最后一个节点，这期间会逐个改变所遍历到的节点的指针域，另其指向前一个节点
    Node * iteration_reverse(Node *head);
    //递归反转法的实现思想是从链表的尾节点开始，依次向前遍历，遍历过程依次改变各节点的指向，即另其指向前一个节点。
    Node * recursive_reverse(Node * head);
    // 链表求中间结点
    // 合并有序链表
    // 删除链表倒数第K个结点

};

class doubleNode
{
public:
    doubleNode() {}
    doubleNode * pre;
    doubleNode * next;
    void setData(int data){this->data = data;}
    int getData(){return this->data;}
private:
    int data;
};

class doubleLinkedList:public doubleNode
{
public:
    doubleLinkedList();
    bool isEmpty();
    doubleNode *getNode(int index);
    int size();
    void insert(int data, int index);
    void traversal();
    void remove(int index);

private:
    doubleNode *head;

};

class cycleLinkedList:public Node
{
public:
    cycleLinkedList();
    void insert(Node * node);
private:
    Node * head;
};


void testRunLinkList();

#endif // LINKLIST_H
